﻿#include <iostream>
#include <tgmath.h>
#include<string>
#include<algorithm>
#include <vector>
using namespace std;

////计算square是几位数
//int fun(int s)
//{
//    int count = 1;
//    while(s > 10)
//    {
//        count++;
//        s /= 10;
//    }
//    return count;
//}
//
//int get_tail(int n,int i)
//{
//    int number = fun(n)-1;
//    if (n > 100)
//    {
//        int a = pow(10, number);
//        while (n>0)
//        {
//            n %= a;
//            a /= 10;
//            if (n == i)
//            {
//                return n;
//                break;
//            }
//        }
//    }
//    return n % 10;
//}
//int main() {
//    int n;
//    int count = 0;
//    int square = 0;
//    while (cin >> n)
//    {
//        for (int i = 0; i <= n; i++)
//        {
//            square = pow(i, 2);
//            int ret = get_tail(square,i);
//            if(ret==i)
//            {
//                cout << i << " ";
//                count++;
//            }
//        }
//        cout << endl;
//        cout << count << endl;
//    }
//}



//bool canPermutePalindrome(string s)
//{
//    sort(s.begin(), s.end());
//    string::iterator it = s.begin();
//    if (s.size() == 1)
//    {
//        return true;
//    }
//
//    while (it != s.end())
//    {
//        if (*it != *(it + 1))
//        {
//            return false;
//        }
//        else
//        {
//            it += 2;
//            if (*(it + 1) == '\0')
//            {
//                return true;
//            }
//            if (*it != *(it + 1))
//            {
//                if (*(it + 2) == *(s.end()-1))
//                {
//                    return true;
//                }
//                return false;
//            }
//
//        }
//    }
//    return true;
//}
//
//int main()
//{
//    string s("tactcoa");
//    bool ret = canPermutePalindrome(s);
//    cout << ret << endl;
//    return 0;
//}




void duplicateZeros(vector<int>& arr)
{
    int cur = 0;
    int dest = -1;
    int n = arr.size();
    while (cur < n)
    {
        if (arr[cur])
        {
            dest++;
        }
        else
        {
            dest += 2;
        }
        if (dest >= n - 1)
        {
            break;
        }
        cur++;
    }

    if (dest == n)
    {
        arr[n - 1] = 0;
        cur--;
        dest -= 2;
    }
    while (cur >= 0)
    {
        if (arr[cur])
        {
            arr[dest] = arr[cur];
            dest--;
            cur--;
        }
        else
        {
            arr[dest] = 0;
            dest--;
            arr[dest] = 0;
            dest--;
            cur--;
        }
    }
}

//void duplicateZeros(vector<int>& arr)
//{
//    // 1. 先找到最后⼀个数
//    int cur = 0, dest = -1, n = arr.size();
//    while (cur < n)
//    {
//        if (arr[cur]) dest++;
//        else dest += 2;
//        if (dest >= n - 1) break;
//        cur++;
//    }
//    // 2. 处理⼀下边界情况
//    if (dest == n)
//    {
//        arr[n - 1] = 0;
//        cur--; dest -= 2;
//    }
//    // 3. 从后向前完成复写操作
//    while (cur >= 0)
//    {
//        if (arr[cur]) arr[dest--] = arr[cur--];
//        else
//        {
//            arr[dest--] = 0;
//            arr[dest--] = 0;
//            cur--;
//        }
//    }
//}
//int main()
//{
//    vector<int> v;
//    v.push_back(0);
//    v.push_back(0);
//    v.push_back(0);
//    v.push_back(0);
//    v.push_back(0);
//    v.push_back(0);
//    v.push_back(0);
//
//    for (auto e : v)
//    {
//        cout << e << " ";
//    }
//
//    duplicateZeros(v);
//    cout << endl;
//    for (auto e : v)
//    {
//        cout << e << " ";
//    }
//    return 0;
//}

//int main()
//{
//    int n = 0;
//    string s;
//    int mid = 0;
//    while (cin >> n)
//    {
//        getchar();
//        for (int i = 0; i < n; i++)
//        {
//            getline(cin, s);
//            if (s.size() >= 10)
//            {
//                char left = *s.begin();
//                char right = *(s.end()-1);
//                mid = s.size() - 2;
//                cout << left << mid << right << endl;
//            }
//            else
//            {
//                cout << s << endl;
//            }
//
//        }
//    }
//    return 0;
//}

//int main()
//{
//    std::string str("now step live...");
//    for (std::string::reverse_iterator rit = str.rbegin(); rit != str.rend(); ++rit)
//    std::cout << *rit;
//    return 0;
//}
string replaceSpaces(string S, int length)
{
    string tmp(S.begin(), S.begin() + length);
    string::iterator it = tmp.begin();
    int count = 0;
    while (it != tmp.end())
    {
        if (*it == ' ')
        {
            count++;
        }
        it++;
    }
    it = tmp.begin();
    string str;
    while (it != tmp.end())
    {
        if (str.size() < 2 * count + tmp.size() || str.size() < S.size())
        {
            if (*it != ' ')
            {
                str.push_back(*it);
            }
            else
            {
                str.push_back('%');
                str.push_back('2');
                str.push_back('0');
            }
            it++;
        }
    }
    return str;
}
//int main()
//{
//    string s("ds sdfs afs sdfa dfssf asdf             ");
//    int length = 27;
//    string tmp = replaceSpaces(s, length);
//    cout << tmp << endl;
//    return 0;
//}


string compressString(string S)
{
    int count = 1;
    string tmp;
    string::iterator it = S.begin();
    while (it != S.end())
    {
        while(it + 1 != S.end() && *it == *(it + 1))
        {
            count++;
            it++;
            if (it + 1 != S.end() && *it != *(it + 1))
            {
                tmp.push_back(*it);
                tmp.append(to_string(count));
                count = 1;
                it++;
            }
        }
        tmp.push_back(*it);
        tmp.append(to_string(count));
        it++;
    }
    if (tmp.size() >= S.size())
    {
        return S;
    }
    return tmp;
}

//int main()
//{
//    string S("aabcccccaaa");
//    string ret = compressString(S);
//    cout << ret << endl;
//    return 0;
//}

//void transfer()
//{
//    int n;     //要转化的个位数字
//    cout << "输入数字：";
//    cin >> n;
//
//    char ch;
//    ch = n + '0';     //利用数字在ASCII中与0的相对位置
//
//    cout << "转化结果为：" << ch << endl;
//}

//int main()
//{
//    transfer();
//
//    return 0;
//}


//替换为它每个位置上的数字的平方和
int fun(int n)
{
    int count = 0;
    int i = 0;
    while (n > 0)
    {
        i = n % 10;
        count += pow(i, 2);
        n /= 10;
    }
    return count;
}
bool isHappy(int n)
{
    int slow = n, fast = n;
    int i = 1, j = 2;
    while (n)
    {
        while (i)
        {
            slow = fun(slow);
            i--;
        }
        while (j)
        {
            fast = fun(fast);
            j--;
        }
        i = 1;
        j = 2;
        if (fast == slow)
        {
            break;
        }
    }
    if (fast == 1)
    {
        return true;
    }
    return false;
}



//int fun(int n)
//{
//    int count = 0;
//    int i = 0;
//    while (n > 0)
//    {
//        i = n % 10;
//        count += pow(i, 2);
//        n /= 10;
//    }
//    return count;
//}
//bool isHappy(int n)
//{
//    int slow = n, fast = fun(n);
//    while (slow != fast)
//    {
//        slow = fun(slow);
//        fast = fun(fun(fast));
//    }
//    return fast == 1;
//}

//int main()
//{
//    cout << isHappy(19) << endl;
//    return 0;
//}


//利用单调性 使用双指针
int maxArea(vector<int>& height)
{
    int left = 0;
    int right = height.size() - 1;
    int maxv = 0;
    int v = 0;
    while (left != right)
    {
        v = (right - left) * (height[left] > height[right] ? height[right] : height[left]);

        if (v > maxv)
        {
            maxv = v;
        }
        //谁小移动谁
        if (height[left] < height[right])
        {
            left++;
        }
        else
        {
            right--;
        }
    }
    return maxv;
}

int main()
{
    vector<int> v{ 1, 8, 6, 2, 5, 4, 8, 3, 7 };
    int ret =maxArea(v);
    cout << ret;
    return 0;
}


int main()
{
    return 0;
}